from typing import List


class Solution:
    """
    方法：旋转图像
    通过先转置矩阵再水平翻转每一行来实现90度顺时针旋转

    Args:
        matrix: List[List[int]] - 输入的n x n二维矩阵

    Returns:
        None - 直接修改原矩阵

    Time: O(n^2) - 需要遍历矩阵中的所有元素
    Space: O(1) - 原地修改，不需要额外空间
    """
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        # 第一步：转置,(i,j) -> (j,i)
        for i in range(n):
            for j in range(i): # 遍历对角线下方元素
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        # 第二步：行翻转 (j,i) -> (j, n-1-i)
        for row in matrix:
            row.reverse()


        